10299. Родственники

По заданному положительному целому числу n вычислить количество чисел, меньших n и взаимно простых с n.

Вход. Каждая входная строка содержит число n (n £ 1.000.000.000). Число n = 0 является концом входных данных и не обрабатывается.

Выход. Для каждого входного числа вывести ответ на вопрос, поставленный в условии задачи.

Пример входа

7
12
0

Пример выхода

6
4

РЕШЕНИЕ

теория чисел – функция Эйлера

Анализ алгоритма

Сведенной системой вычетов Z_n^* называется множество натуральных чисел, меньших n и взаимно простых с n. Ответом на поставленный вопрос будет мощность (количество элементов) множества Z_n^*. Известно, что |Z_n^*| = j(n), где j – функция Эйлера. Если n = – разложение числа n на простые множители, то

j(n) = n * (1 – 1/p₁) * (1 – 1/p₂) * … * (1 – 1/p_t)

При этом следует помнить, что для n = 1 ответом будет 0 (не существует ни одного целого положительного числа, меньшего 1).

Пример

Рассмотрим второй тест. Сведенная система вычетов по модулю 12 имеет вид: Z₁₂^* = {1, 5, 7, 11}, ее мощность равна |Z₁₂^*| = 4. Этот же результат можно получить, вычислив функцию Эйлера: j(12) = j(2² * 3) = 12 * (1 – 1/2) * (1 – 1/3) = 12 * (1/2) * (2/3) = 4.

Реализация алгоритма

В задаче достаточно использовать для целочисленных переменных тип данных int, так как в языке С тип int четырехбайтный (в который помещаются числа до 10⁹). Читаем значение n. Если оно равно 1, то выводим результат 0.

while (scanf("%d",&n) == 1 && n)

{

if (n == 1)

{

printf("0\n"); continue;

}

В переменной result накапливаем значение j(n). Изначально положим result = n. Делители числа n ищем, перебирая все значения i от 2 до . При нахождении делителя i умножаем result на (1 - 1/i) (операция result = result * ( 1 - 1/i) эквивалентна result = result - result / i) и делим значение n на i до тех пор, пока деление производится без остатка (функция Эйлера j(n) зависит только от делителей числа n, а не степеней с которыми они входят в разложение n на множители).

result = n;

for(i = 2; i <= sqrt(1.0*n); i++)

{

if (n % i == 0) result -= result / i;

while (n % i == 0) n /= i;

}

Если после выполнения цикла значение n все еще больше 1, то исходное значение n содержало делитель, больший . И текущее n как раз равно этому делителю. Учтем его в формуле вычисления функции Эйлера. После чего выведем результат.

if (n > 1) result -= result / n;

printf("%d\n",result);

}